#include<bits/stdc++.h>
using namespace std;
class Trie
{
    public:
        Trie()
        {
            children=vector<Trie*>(26);
            flag=false;
            count=0;
        }
        void insert(const string& s)
        {
            Trie* cur=this;
            for(char ch:s)
            {
                int k=ch-'a';
                if(cur->children[k]==nullptr) cur->children[k]=new Trie();
                cur->children[k]->count++;
                cur=cur->children[k];
            }
            cur->flag=true;
        }
        int search(const string& s)
        {
            Trie* cur=this;
            int ret=0;
            int n=s.size();
            for(int i=0;i<n;i++)
            {
                int k=s[i]-'a';
                if(i==n-1&&cur->children[k]!=nullptr) return cur->children[k]->count; 
            }
            return 0;
        }
    private:
        vector<Trie*> children;
        bool flag;
        int count;
};



class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        Trie* root=new Trie();
        Trie* cur=root;
        int m=words.size();
        vector<int> ret(m);
        for(const string& s:words)  root->insert(s);
        for(int i=0;i<m;i++)
        {
            string s=words[i];
            string t="";
            for(char ch:s)
            {
                t+=ch;
                ret[i]+=root->search(t);
            }
        }
        return ret;
    }
};

int main()
{
    vector<string> vec={"abc","ab","bc","b"};
    Solution so;
    so.sumPrefixScores(vec);
    return 0;
}